package c_leetcode.a_121_best_time_buy;

/**
 * 贪心算法
 * 时间复杂度    O(n)
 * 空间复杂度    O(1)
 * ------
 * 贪心特点：求问题最优结构，每次只关注局部最优，希望通过局部最优选择到全局最优
 * 1.局部最优解 -> 局部最优解是i天最低价买入，j(j > i)天最高价卖出，思路就在找到i，以及后续的max(x-i)
 * 2.无后效性 -> 第i天更新了最低价格，那么i+1天开始，只需要关注i天之后的价格，而不需要关注第i天前的价格
 * 3.存在多个局部最优解，但是我们记录了全局的最优解，例子如下
 * ------
 * 2 10 (当前局部最优8)  1 7 (当前局部最优6)
 *      (替换全局最优8)      (无法替换全局最优)
 * @author FRSF
 * @since 2025/3/5 22:25
 */
public class Greedy {
    public static void main(String[] args) {
        System.out.println(new Greedy().maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }

    public int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
}
